/**
 * 
 */
package com.gwcloud.leetcode.tags.dp;

/**
 * @ClassName   : Leetcode0887 
 * @author      : ganwei 
 * @date        : 2020年5月15日
 * @Description : Leetcode0887 鸡蛋掉落
 */
public class Leetcode0887 {
    /**
     * -解题思路，动态规划
     */
	public int superEggDrop(int K, int N) {
    	//状态转移矩阵
		int[][] dp = new int[K+1][N+1];
		//初始化N=0的情况
		for(int i = 0; i <= K; i++){
			dp[i][0] = 0;
		}
		//初始化K=1的情况
		for(int i = 1; i <= N; i++){
			dp[0][i] = 0;
			dp[1][i] = i;
		}

		
		for(int i = 2; i <= K; i++){
			for(int j = 1; j <= N; j++){
				int res = j;
				for(int t = 1; t <= j; t++){
					res = Math.min(res, Math.max(dp[i][j-t], dp[i-1][t-1])+1);
				}
				dp[i][j] = res;
			}
		}
		
    	return dp[K][N];
    }
	/**
	 * -优化的动态规划，该状态转移矩阵用的有点妖气
	 */
	public int superEggDrop_1(int K, int N) {
    	//状态转移矩阵
		int[][] dp = new int[K+1][N+1];
		int m = 0;
		while(dp[K][m] < N) {
			m++;
			for(int k = 1; k <= K; k++) {
				dp[k][m] = dp[k][m-1] +dp[k-1][m-1]+1;
			}
		}
		return m;

	}
	
	/**
	 * 主函数
	 */
    public static void main(String[] args){
    	Leetcode0887 l0887 = new Leetcode0887();
    	System.out.println(l0887.superEggDrop_1(1, 3));
    	
    }
}
